// 比较函数类型，用于排序
type CompareFn<T> = (a: T, b: T) => number;

// 菱形A*算法位置类型
type DiamondAStarPos = {
    row: number;       // 行号
    col: number;       // 列号
    step: number;      // 当前步数
    searched: boolean; // 是否被搜索过
    opened: boolean;   // 是否在开放列表中
    closed: boolean;   // 是否在封闭列表中
    weight?: number;   // 当前位置的权重
    prev?: DiamondAStarPos; // 前一个位置，用于追踪路径
}

// A*算法的位置类型
type AStarPos = {
    row: number;       // 行号
    col: number;       // 列号
    step: number;      // 当前步数
    searched: boolean; // 是否被搜索过
    opened: boolean;   // 是否在开放列表中
    closed: boolean;   // 是否在封闭列表中
    weight?: number;   // 当前位置的权重
    prev?: AStarPos;   // 前一个位置，用于追踪路径
}

// 菱形A*地图类型
type DiamondAStarMap = DiamondAStarPos[][];

// A*算法的配置
const AStarConfig = {
    toStartWeight: 1,  // 从起点到当前位置的权重
    toEndWeight: 1     // 从当前位置到终点的权重
}

/** 主函数，寻找菱形格子路径 
 * @example
    const map = []
    for (let i = 0; i < 48; i++) {
        map[i] = []
        for (let j = 0; j < 8; j++) {
            map[i].push(1)
        }
    }
    map[19][2] = 0
    map[19][3] = 0
    map[19][4] = 0
    map[19][5] = 0
    // 定义起点和终点
    const startPos: [number, number] = [2, 2]; 
    const endPos: [number, number] = [45, 5];   
    const path = findDiamondRoad(map, startPos, endPos)
*/
export const findDiamondRoad = (gameMap: any[][], startPos: [number, number], endPos: [number, number]) => {
    // 检查输入参数的合法性
    if (!Array.isArray(gameMap) || !Array.isArray(startPos) || !Array.isArray(endPos)) {
        console.error("Invalid input parameters");
        return []
    }

    // 创建菱形A*地图
    let diamondAStarMap: DiamondAStarMap = gameMap.map((row, rowIndex) =>
        row.map((col, colIndex) => ({
            row: rowIndex,
            col: colIndex,
            step: 0,
            searched: false,
            opened: false,
            closed: !col, // 如果地图位置为 false，则设置为封闭
        }))
    );

    // 使用A*算法找到路径
    let diamondRoad = diamondAStarFindRoad(diamondAStarMap, startPos, endPos);

    // 返回路径点的坐标
    return diamondRoad.map(diamondPos => [diamondPos.row, diamondPos.col]);
}

// A*算法的核心函数，寻找路径
const diamondAStarFindRoad = (map: DiamondAStarMap, [startRow, startCol]: [number, number], [endRow, endCol]: [number, number]) => {
    let road: DiamondAStarPos[] = []; // 用于存储最终路径
    let openList: DiamondAStarPos[] = []; // 开放列表，用于存储待检查的位置
    let testList: DiamondAStarPos[] = []; // 测试列表，用于存储已检查的位置

    let startPos = map[startRow][startCol];
    let endPos = map[endRow][endCol];

    // 检查起点或终点是否被阻挡
    if (startPos.closed || endPos.closed) {
        console.error("Start or end position is blocked");
        return []
    }
    // 初始化起点
    startPos.searched = true;
    startPos.opened = true;
    startPos.weight = calWeight(0, calDistance(startPos, endPos));
    openList.push(startPos);

    let testPos = openList.shift();
    while (testPos) {
        testPos.opened = false;
        testList.push(testPos);

        // 如果当前位置是终点，构建并返回路径
        if (equalsPos(testPos, endPos)) {
            let roadPos: DiamondAStarPos | undefined = endPos;
            while (roadPos) {
                road.push(roadPos);
                roadPos = roadPos.prev;
            }
            return road.reverse();
        }

        // 获取周围未被搜索的位置
        let notSearchedPosList = getDiamondNotSearchedPosList(map, testPos);
        if (notSearchedPosList.length > 0) {
            notSearchedPosList.forEach(notSearchedPos => {
                if (testPos.prev && lineOfSight(map, testPos.prev, notSearchedPos)) {
                    // 如果前一个位置和当前未搜索的位置之间有视线
                    let newStep = testPos.prev.step + 1;
                    let newWeight = calWeight(newStep, calDistance(notSearchedPos, endPos));
                    if (!notSearchedPos.weight || notSearchedPos.weight > newWeight) {
                        notSearchedPos.prev = testPos.prev;
                        notSearchedPos.step = newStep;
                        notSearchedPos.weight = newWeight;
                    }
                } else {
                    // 如果没有视线，则按普通A*算法处理
                    let newStep = testPos.step + 1;
                    let newWeight = calWeight(newStep, calDistance(notSearchedPos, endPos));
                    if (!notSearchedPos.weight || notSearchedPos.weight > newWeight) {
                        notSearchedPos.prev = testPos;
                        notSearchedPos.step = newStep;
                        notSearchedPos.weight = newWeight;
                    }
                }
                addToOpenList(openList, notSearchedPos);
            });
        } else {
            testPos.closed = true; // 标记当前测试的位置为封闭
        }

        testPos = openList.shift();
    }

    console.error("Road not found");
    return []
}

// 获取周围未被搜索的位置，适用于菱形格子
const getDiamondNotSearchedPosList = (map: DiamondAStarMap, pos: DiamondAStarPos) => {
    let aroundPosList: [number, number][] = [];
    if (pos.row % 2 === 0) {
        // 偶数行
        aroundPosList = [
            [pos.row - 1, pos.col],     // 上一行的同列
            [pos.row - 1, pos.col - 1], // 上一行的右列
            [pos.row + 1, pos.col],     // 下一行的同列
            [pos.row + 1, pos.col - 1], // 下一行的右列
        ];
    } else {
        // 奇数行
        aroundPosList = [
            [pos.row - 1, pos.col],     // 上一行的同列
            [pos.row - 1, pos.col + 1], // 上一行的左列
            [pos.row + 1, pos.col],     // 下一行的同列
            [pos.row + 1, pos.col + 1], // 下一行的左列
        ];

    }

    let notSearchedPosList: DiamondAStarPos[] = [];

    aroundPosList.forEach(aroundPos => {
        let [row, col] = aroundPos;
        // 检查位置是否在地图范围内
        if (row >= 0 && row < map.length && col >= 0 && col < map[row].length) {
            let pos = map[row][col];
            // 如果位置未被搜索且未在开放列表中且未封闭，则加入未搜索列表
            if (!pos.searched && !pos.opened && !pos.closed) {
                pos.searched = true;
                notSearchedPosList.push(pos);
            }
        }
    });

    return notSearchedPosList;
}

// 插入元素到有序列表的函数
const appendToOrderList = <T>(orderList: T[], item: T, compare: CompareFn<T>) => {
    let left = 0;
    let right = orderList.length;

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (compare(item, orderList[mid]) <= 0) {
            right = mid; // 如果 item 小于等于当前中点元素，则缩小右边界
        } else {
            left = mid + 1; // 否则，缩小左边界
        }
    }

    // 在计算出的位置插入元素
    orderList.splice(left, 0, item);
}

// 计算两个位置之间的曼哈顿距离
const calDistance = (pos0: AStarPos, pos1: AStarPos) => {
    let dRow = pos0.row - pos1.row;
    let dCol = pos0.col - pos1.col;
    return Math.abs(dRow) + Math.abs(dCol);
}

// 计算权重的函数
const calWeight = (toStart: number, toEnd: number) => {
    return AStarConfig.toStartWeight * toStart + AStarConfig.toEndWeight * toEnd;
}

// 将位置添加到开放列表中
const addToOpenList = (openList: AStarPos[], pos: AStarPos) => {
    pos.opened = true;
    appendToOrderList(openList, pos, (pos0, pos1) => {
        if (pos0.weight !== undefined && pos1.weight !== undefined) {
            return pos0.weight - pos1.weight;
        }
        return 0;
    });
}

// 检查两个位置是否相等
const equalsPos = (pos0: AStarPos, pos1: AStarPos) => {
    return pos0.row === pos1.row && pos0.col === pos1.col;
}

/** 检查两个位置之间是否有视线
 * @param map - 菱形A*地图
 * @param pos0 - 起始位置
 * @param pos1 - 目标位置
 * @returns 如果两个位置之间没有障碍物则返回true，否则返回false
 */
const lineOfSight = (map: DiamondAStarMap, pos0: DiamondAStarPos, pos1: DiamondAStarPos): boolean => {
    let x0 = pos0.row;
    let y0 = pos0.col;
    let x1 = pos1.row;
    let y1 = pos1.col;

    let dx = Math.abs(x1 - x0);
    let dy = Math.abs(y1 - y0);

    let sx = (x0 < x1) ? 1 : -1;
    let sy = (y0 < y1) ? 1 : -1;

    let err = dx - dy;

    // 浮点除法修正，防止因误差导致漏掉节点
    const errorAdjust = 0.5;

    while (true) {
        // 检查边界
        if (x0 < 0 || x0 >= map.length || y0 < 0 || y0 >= map[0].length) {
            return false;
        }

        // 如果路径上有障碍，返回false
        if (map[x0][y0].closed) return false;

        // 如果到达终点，返回true
        if (x0 === x1 && y0 === y1) return true;

        let e2 = err * 2;

        // 处理浮点误差
        if (e2 > -dy + errorAdjust) {
            err -= dy;
            x0 += sx;
        }
        if (e2 < dx + errorAdjust) {
            err += dx;
            y0 += sy;
        }

        // 额外的对角线检查
        // 检查当前点和目标点之间是否有障碍物
        if (e2 > -dy + errorAdjust && e2 < dx + errorAdjust) {
            if (map[x0][y0 - sy] && map[x0][y0 - sy].closed) return false;
            if (map[x0 - sx] && map[x0 - sx][y0] && map[x0 - sx][y0].closed) return false;
        }
    }
}
